package com.cango.student.algorithm.sort;

/**
 * 快速排序
 * 时间复杂度（平均）	时间复杂度（最坏)	时间复杂度（最好)	空间复杂度	稳定性	复杂性
 * O(nlog2n) 	       O(n2)	      O(nlog2n)	    O(nlog2n)	不稳定	较复杂
 */
public class Quicksort3 {

    static int[] a = {40, 9, 20, 4, 30, 1, 54, 6, 8, 99};
    //    static int[] a = {6,11,3,9,8};
    static int n;

    public static void quicksort(int left, int right) {
        if (left > right)
            return;

        int temp = a[right];
        int i = left;
        int j = left;

        while (j < right) {
            if (a[j] < temp) {
                if (i != j) {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
                i++;
            }
            j++;
        }
        a[right] = a[i];
        a[i] = temp;

        quicksort(left, i-1);
        quicksort(i+1, right);

    }

    public static void main(String[] args) {
        n = a.length - 1;

        for (int i = 0; i <= n; i++)
            System.out.print(a[i] + " ");

        quicksort(0, n); //快速排序调用
        System.out.println("");
        //输出排序后的结果
        for (int i = 0; i <= n; i++)
            System.out.print(a[i] + " ");
    }
}
